#pragma once
#include"BinaryTreeBase.h"

//链表实现栈
typedef struct TreeNodeStack {
	BinaryTreeNode* data;
	TreeNodeStack* next;
}TreeNodeStack;

//初始化
TreeNodeStack* InitTreeNodeStack() {
	TreeNodeStack* s = (TreeNodeStack*)malloc(sizeof(TreeNodeStack));
	s->data = NULL;
	s->next = NULL;
	return s;
}

//栈是否为空
bool IsEmpty(TreeNodeStack *s) {
	if (s->next == nullptr) {
		return true;
	}
	return false;
}

//入栈
//先进后出, s->next 指向最后一个元素
//   s
//   ↓
// nodeN -> ... -> node2 -> node1 -> node0
//往里压进, 而不是往后加入
void Push(BinaryTreeNode* node, TreeNodeStack* s) {
	TreeNodeStack* sNode = (TreeNodeStack*)malloc(sizeof(TreeNodeStack));
	sNode->data = node;
	sNode->next = s->next;

	s->next = sNode;
}

//出栈
TreeNodeStack* Pop(TreeNodeStack *s) {
	if (!IsEmpty(s)) {
		TreeNodeStack* sNode = s->next;
		s->next = sNode->next;
		sNode->next = NULL;
		return sNode;
	}
	
	else {
		return NULL;
	}
}

//获取栈顶元素
TreeNodeStack* GetTop(TreeNodeStack* s) {
	if (!IsEmpty(s)) {
		TreeNodeStack* sNode = s->next;
		return sNode;
	}

	else {
		return NULL;
	}
}


//使用迭代前序遍历二叉树
void PreTravelBinaryTreeLoop(BinaryTreeNode *T) {
	TreeNodeStack* s = InitTreeNodeStack();
	BinaryTreeNode* node = T;

	//当节点存在 或者 栈不为空
	while (node != NULL || !IsEmpty(s)) {
		if (node != NULL) {
			//先访问节点
			cout << node->data << " ";
			//入栈
			Push(node, s);
			//访问左子树
			node = node->LChild;
		}
		else {
			//左子树不存在, 出栈
			TreeNodeStack* sNode = Pop(s);
			//访问右子树
			node = sNode->data->RChild;
			free(sNode);
		}
	}
}

//使用迭代中序遍历二叉树
void InTravelBinaryTreeLoop(BinaryTreeNode* T) {
	TreeNodeStack* s = InitTreeNodeStack();
	BinaryTreeNode* node = T;

	while (node != NULL || !IsEmpty(s)) {
		if (node != NULL) {
			//入栈
			Push(node, s);
			//访问左子树
			node = node->LChild;
		}
		else {
			//左子树不存在, 出栈
			TreeNodeStack* sNode = Pop(s);
			//访问出栈的节点
			cout << sNode->data->data << " ";
			//访问右子树
			node = sNode->data->RChild;
			free(sNode);
		}
	}
}

//使用迭代后序遍历二叉树
void BackTravelBinaryTreeLoop(BinaryTreeNode* T) {
	TreeNodeStack* s = InitTreeNodeStack();
	BinaryTreeNode* node = T;
	while (node != NULL || !IsEmpty(s)) {
		if (node != NULL) {
			//入栈
			Push(node, s);
			//访问左子树
			node = node->LChild;
		}
		else {
			//左子树不存在, 访问栈顶元素
			BinaryTreeNode* topNode = GetTop(s)->data;

			//判断右子树是否存在, 并且判断右子树是否被访问(访问过则不会继续访问, 否则死循环)
			if (topNode->RChild != NULL && !(topNode->RChild->isCall)) {
				//将右子树入栈
				topNode = topNode->RChild;
				topNode->isCall = true;
				Push(topNode, s);
				//访问左子树
				node = topNode->LChild;
			}
			else {
				//右子树不存在, 或者右子树被访问过, 出栈
				TreeNodeStack* sNode = Pop(s);
				//访问出栈元素
				cout << sNode->data->data << " ";
				free(sNode);
			}
		}
	}
}